package com.wtgroup.demo.leetcode.org_bytedance;

import com.wtgroup.demo.common.util.InputParseUtil;

import java.util.List;

/**
 * 695. 岛屿的最大面积 https://leetcode-cn.com/problems/max-area-of-island/
 * @author dafei
 * @version 0.1
 * @date 2021/4/29 19:22
 */
public class Q_岛屿的最大面积 {

    public static void main(String[] args) {
        List parse = InputParseUtil.parse("[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]");
        // List parse = InputParseUtil.parse("[[1]]");
        int[][] input = InputParseUtil.listToArray2Int(parse);
        int i = new Q_岛屿的最大面积().maxAreaOfIsland(input);
        System.out.println(i);

        int[][] input2 = InputParseUtil.listToArray2Int(parse);
        System.out.println(new Q_岛屿的最大面积().maxAreaOfIsland_2(input2));

    }


    /**
     * 等价LC的 "方法一：深度优先搜索". 另, LC上几种方式, 本质都是一样.
     * 故, 记住自己最熟悉的即可. "感染"思想是关键.
     */
    public int maxAreaOfIsland(int[][] grid) {

        int rowCnt = grid.length;
        int colCnt = grid[0].length;
        int cnt = 0;
        for (int i = 0; i < rowCnt; i++) {
            int[] row = grid[i];
            for (int j = 0; j < colCnt; j++) {
                if (1 == row[j]) {
                    int res = infect(i, j, grid, rowCnt, colCnt);
                    cnt = Math.max(cnt, res);
                }
            }
        }
        return cnt;
    }

    // 感染后, 返回被感染的数目
    private int infect(int row, int col, int[][] grid, int rowCnt, int colCnt) {
        // 越界了 or 当前非1 , 退出递归. (如此, 下面无脑进递归即可, 无需考虑邻近是否是1)
        if (row < 0 || row == grid.length || col < 0 || col == grid[0].length || grid[row][col]!=1) {
            return 0;
        }

        // 感染
        grid[row][col] = 0;
        int infected = 1;

        // 上
        infected += infect(row - 1, col, grid, rowCnt, colCnt);
        // 下
        infected += infect(row + 1, col, grid, rowCnt, colCnt);
        // 左
        infected += infect(row, col - 1, grid, rowCnt, colCnt);
        // 右
        infected += infect(row, col + 1, grid, rowCnt, colCnt);

        return infected;
    }

    //------------------------------------------------------------------------------------------------------------------
    // 连通分量方式 todo 不对
    //------------------------------------------------------------------------------------------------------------------
    /*
     * # 如何区分元素指向
     * M1: 左的方式: 用一个空对象替换二维数组中的整数, 借助引用类型地址来区分.
     * M2: 我的方式, 行列封装到对象里装起来.
     * M3: 在行*列不会溢出的前提下, 将 行*列 转为单个数组.
     */

    public int maxAreaOfIsland_2(int[][] grid) {

        UnionFind unionFind = new UnionFind(grid);
        return unionFind.maxCnt;
    }

    static class UnionFind {
        int[][] grid;
        // i,j -> (k,m)
        Pos[][] pars;
        int[][] counter;
        int maxCnt = 0;

        public UnionFind(int[][] grid) {
            this.grid = grid;
            int rowCnt = grid.length;
            int colCnt = grid[0].length;
            pars = new Pos[rowCnt][];
            counter = new int[rowCnt][];
            // 初始化
            for (int i = 0; i < rowCnt; i++) {
                pars[i] = new Pos[colCnt];
                counter[i] = new int[colCnt];
                for (int j = 0; j < colCnt; j++) {
                    // 1 位置, 连通1个
                    if (grid[i][j] == 1) {
                        // 和自己连通
                        pars[i][j] = new Pos(i,j);
                        counter[i][j] = 1;
                        // maxCnt 至少为1了
                        maxCnt = 1;
                    }
                }
            }

            // 连通
            for (int i = 0; i < rowCnt; i++) {
                for (int j = 0; j < colCnt; j++) {
                    if (grid[i][j] != 1) {
                        continue;
                    }
                    // 上
                    if (i > 0 && grid[i-1][j] == 1) {
                        union(i - 1, j, i, j);
                    }
                    // 左
                    if (j > 0 && grid[i][j-1] == 1) {
                        union(i, j - 1, i, j);
                    }
                }
            }
        }

        public void union(int ai, int aj, int bi, int bj) {
            Pos aRoot = find(ai, aj);
            Pos bRoot = find(bi, bj);
            if (aRoot != bRoot) {
                // 合并, 更新 maxCnt
                // 小挂到大
                Pos small = aRoot;
                Pos big = bRoot;
                if (counter[aRoot.row][aRoot.col] > counter[bRoot.row][bRoot.col]) {
                    small = bRoot;
                    big = aRoot;
                }
                pars[small.row][small.col] = big;
                counter[big.row][big.col] += counter[small.row][small.col];
                maxCnt = Math.max(counter[big.row][big.col], maxCnt);
            }
        }

        // 找根
        public Pos find(int i, int j) {
            Pos parent = pars[i][j];
            // 当前位置指向的是自己=>root
            if (parent.eq(i,j)) {
                return parent;
            }
            Pos root = find(parent.row, parent.col);
            // 沿途都指向 root (打平)
            pars[i][j] = root;
            return root;
        }


    }

    // static class Dot {}

    /**
     * M1: 左的方式: 用一个空对象替换二维数组中的整数, 借助引用类型地址来区分.
     * M2: 我的方式, 行列封装到对象里装起来.
     * M3: 在行*列不会溢出的前提下, 将 行*列 转为单个数组.
     */
    static class Pos {
        int row;
        int col;

        public Pos(int row, int col) {
            this.row = row;
            this.col = col;
        }

        public boolean eq(int i, int j) {
            return this.row == i && this.col == j;
        }

        // @Override
        // public boolean equals(Object obj) {
        //     if (obj==null || !(obj instanceof Pos)) {
        //         return false;
        //     }
        //     return this == obj || (this.row == ((Pos) obj).row && this.col == ((Pos) obj).col);
        // }
    }


}
